﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace DataStuctureStudy.Graphs
{
    class WeightedGraph
    {
        public static void Test()
        {
            var graph = new Graph<String>(50);
            graph
                .AddVertex("A")
                .AddVertex("B")
                .AddVertex("C")
                .AddVertex("D")
                .AddVertex("E");

            graph
                .AddUnDirectedEdge("A", "B", 5)
                .AddUnDirectedEdge("A", "D", 7)
                .AddUnDirectedEdge("B", "C", 6)
                .AddUnDirectedEdge("B", "D", 8)
                .AddUnDirectedEdge("B", "E", 7)
                .AddUnDirectedEdge("C", "E", 9)
                .AddUnDirectedEdge("D", "E", 6);

            var trees = graph.GetShortestPath("A", "E").Select(x => x.Description);
            Console.WriteLine(String.Join(",", trees.ToArray()));
        }

        class PriorityQueue<T>
            where T : IComparable<T>
        {
            private T[] _items;
            private int _length;

            public PriorityQueue(int size)
            {
                _items = new T[size];
            }

            public void EnQueue(T item)
            {
                if (this.IsFull())
                {
                    throw new InvalidOperationException("容量已满，不能插入！");
                }

                _items[_length++] = item;
                this.MoveUp(_length - 1);
            }

            private void MoveUp(int index)
            {
                var bottom = _items[index];
                var current = index;

                while (current > 0)
                {
                    var parent = (current - 1) / 2;
                    if (_items[parent].CompareTo(bottom) < 0)
                    {
                        break;
                    }

                    _items[current] = _items[parent];
                    current = parent;
                }

                _items[current] = bottom;
            }

            public T DeQueue()
            {
                if (this.IsEmpty())
                {
                    throw new InvalidOperationException("容量已空，不能删除！");
                }

                var result = _items[0];
                _items[0] = _items[--_length];

                this.MoveDown(0);

                return result;
            }

            private void MoveDown(int index)
            {
                var top = _items[index];
                var current = index;

                while (current < _length)
                {
                    var small = 0;
                    var left = 2 * current + 1;
                    var right = left + 1;

                    if (left < _length && right < _length)
                    {
                        if (_items[left].CompareTo(_items[right]) <= 0)
                        {
                            small = left;
                        }
                        else
                        {
                            small = right;
                        }
                    }
                    else if (left < _length)
                    {
                        small = left;
                    }
                    else
                    {
                        break;
                    }

                    if (_items[small].CompareTo(top) >= 0)
                    {
                        break;
                    }

                    _items[current] = _items[small];
                    current = small;
                }

                _items[current] = top;
            }

            public bool IsFull()
            {
                return _length == _items.Length;
            }

            public bool IsEmpty()
            {
                return _length == 0;
            }
        }

        class Edge : IComparable<Edge>
        {
            public int StartIndex { get; set; }

            public int EndIndex { get; set; }

            public int Weight { get; set; }

            public string Description { get; set; }

            public int CompareTo(Edge other)
            {
                return this.Weight.CompareTo(other.Weight);
            }
        }

        private class Path : IComparable<Path>
        {
            public Path()
            {
                this.Edges = new List<Edge>();
            }

            public int StartVertexIndex { get; set; }

            public int EndVertexIndex { get; set; }

            public List<Edge> Edges { get; private set; }

            public int Weight { get; private set; }

            public void AddEdges(IEnumerable<Edge> edges)
            {
                foreach (var edge in edges)
                {
                    this.AddEdge(edge);
                }
            }

            public void AddEdge(Edge edge)
            {
                this.Edges.Add(edge);
                this.Weight += edge.Weight;
            }

            public int CompareTo(Path other)
            {
                return this.Weight.CompareTo(other.Weight);
            }
        }

        class Vertex<T>
        {
            public T Value { get; set; }
        }

        class Graph<T>
        {
            #region 私有字段

            private int _maxSize;
            private Vertex<T>[] _vertexs;
            private Edge[][] _edges;
            private int _vertexCount = 0;

            #endregion

            #region 构造方法

            public Graph(int maxSize)
            {
                _maxSize = maxSize;
                _vertexs = new Vertex<T>[_maxSize];
                _edges = new Edge[_maxSize][];
                for (var i = 0; i < _maxSize; i++)
                {
                    _edges[i] = new Edge[_maxSize];
                }
            }

            #endregion

            #region 添加顶点

            public Graph<T> AddVertex(T value)
            {
                _vertexs[_vertexCount++] = new Vertex<T> { Value = value };

                return this;
            }

            #endregion

            #region 添加边

            public Graph<T> AddUnDirectedEdge(T startItem, T endItem, int weight)
            {
                var startIndex = this.GetVertexIndex(startItem);
                var endIndex = this.GetVertexIndex(endItem);

                _edges[startIndex][endIndex] = new Edge { StartIndex = startIndex, EndIndex = endIndex, Weight = weight, Description = String.Format("{0}->{1}", startItem, endItem) };
                _edges[endIndex][startIndex] = new Edge { StartIndex = endIndex, EndIndex = startIndex, Weight = weight, Description = String.Format("{0}->{1}", endItem, startItem) };

                return this;
            }

            public Graph<T> AddDirectedEdge(T startItem, T endItem, int weight)
            {
                var startIndex = this.GetVertexIndex(startItem);
                var endIndex = this.GetVertexIndex(endItem);

                _edges[startIndex][endIndex] = new Edge { StartIndex = startIndex, EndIndex = endIndex, Weight = weight, Description = String.Format("{0}->{1}", startItem, endItem) };

                return this;
            }

            #endregion

            #region 最小生成树

            public IEnumerable<Edge> GetMinimumSpanningTree()
            {
                var minimumSpanningTrees = new List<Edge>();
                Dictionary<int, bool> vertexInTreesTracker = new Dictionary<int, bool>();
                var queue = new PriorityQueue<Edge>(_maxSize);

                var currentVertexIndex = 0;
                while (minimumSpanningTrees.Count < _vertexCount - 1)
                {
                    vertexInTreesTracker[currentVertexIndex] = true;

                    foreach (var item in _edges[currentVertexIndex])
                    {
                        if (item == null)
                        {
                            continue;
                        }
                        if (vertexInTreesTracker.ContainsKey(item.EndIndex))
                        {
                            continue;
                        }

                        queue.EnQueue(item);
                    }

                    var smallEdge = queue.DeQueue();
                    while (vertexInTreesTracker.ContainsKey(smallEdge.EndIndex))
                    {
                        smallEdge = queue.DeQueue();
                    }
                    minimumSpanningTrees.Add(smallEdge);
                    currentVertexIndex = smallEdge.EndIndex;
                }

                return minimumSpanningTrees;
            }

            #endregion

            #region 最短路径

            public IEnumerable<Edge> GetShortestPath(T startItem, T endItem)
            {
                var startIndex = this.GetVertexIndex(startItem);
                var endIndex = this.GetVertexIndex(endItem);

                var shortestPaths = new Dictionary<int, Path>();
                var queue = new PriorityQueue<Path>(_maxSize);

                var currentVertexIndex = startIndex;
                var currentPath = new Path
                {
                    StartVertexIndex = startIndex,
                    EndVertexIndex = endIndex
                };

                while (!shortestPaths.ContainsKey(endIndex))
                {
                    foreach (var item in _edges[currentVertexIndex])
                    {
                        if (item == null)
                        {
                            continue;
                        }
                        if (shortestPaths.ContainsKey(item.EndIndex))
                        {
                            continue;
                        }

                        var path = new Path
                        {
                            StartVertexIndex = startIndex,
                            EndVertexIndex = item.EndIndex
                        };
                        path.AddEdges(currentPath.Edges);
                        path.AddEdge(item);
                        queue.EnQueue(path);
                    }

                    var smallPath = queue.DeQueue();
                    while (shortestPaths.ContainsKey(smallPath.EndVertexIndex))
                    {
                        smallPath = queue.DeQueue();
                    }
                    shortestPaths[smallPath.EndVertexIndex] = smallPath;
                    currentVertexIndex = smallPath.EndVertexIndex;
                    currentPath = smallPath;
                }

                return shortestPaths[endIndex].Edges;
            }

            #endregion

            #region 帮助方法

            private int GetVertexIndex(T item)
            {
                for (var i = 0; i < _vertexCount; i++)
                {
                    if (_vertexs[i].Value.Equals(item))
                    {
                        return i;
                    }
                }
                return -1;
            }

            #endregion
        }
    }
}
